import javax.xml.bind.ValidationEvent;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @author 03010570
 * @date 2020/07/16
 * describe:    LeetCode : 785、判断二分图    https://leetcode-cn.com/problems/is-graph-bipartite/
 */
public class LeetCode_785 {

    public static void main(String[] args) {
        int[][] ints = new int[][]{{1, 3}, {0, 2}, {1, 3}, {0, 2}};
        System.out.println(new LeetCode_785().isBipartite(ints));

        int[][] ints2 = new int[][]{{1, 2, 3}, {0, 2}, {0, 1, 3}, {0, 2}};
        System.out.println(new LeetCode_785().isBipartite(ints2));
    }

    private static final int UNCOLORED = 0;
    private static final int GREEN = 1;
    private static final int RED = 2;
    private boolean valid;
    private int[] colors;

    /**
     * DFS
     *
     * @param graph
     * @return
     */
    public boolean isBipartite(int[][] graph) {
        int length = graph.length;
        colors = new int[length];
        valid = true;
        for (int i = 0; i < length && valid; i++) {
            if (colors[i] == UNCOLORED) {
                dfs(i, RED, graph);
            }
        }
        return valid;
    }

    private void dfs(int i, int color, int[][] graph) {
        colors[i] = color;
        for (int node : graph[i]) {
            if (colors[node] == UNCOLORED) {
                int tempColor = color == GREEN ? RED : GREEN;
                dfs(node, tempColor, graph);
                if (!valid) {
                    return;
                }
            } else if (colors[node] == color) {
                valid = false;
                return;
            }
        }
    }

    /**
     * BFS 广度优先搜索
     * graph 数组的下标表示 i 个节点
     * 时间复杂度 ： O(M+N)  数量的行数和列数
     * 空间复杂度 ： O(N) 存储颜色的节点
     *
     * @param graph
     * @return
     */


    public static boolean isBipartite1(int[][] graph) {
        int length = graph.length;
        int[] colors = new int[length];
        for (int i = 0; i < length; i++) {
            if (colors[i] == UNCOLORED) {
                Queue<Integer> queue = new LinkedList<>();
                queue.offer(i);
                colors[i] = RED;
                while (!queue.isEmpty()) {
                    Integer node = queue.poll();
                    int color = colors[node];
                    int[] ints = graph[node];
                    for (int anInt : ints) {
                        if (colors[anInt] == UNCOLORED) {
                            queue.offer(anInt);
                            colors[anInt] = color == GREEN ? RED : GREEN;
                        } else if (colors[anInt] == color) {
                            return false;
                        }
                    }
                }
            }

        }
        return true;

    }
}
